We consider the Linear Programming (LP) solution of the Compressed Sensing(CS) problem over reals, also known as the Basis Pursuit (BasP) algorithm. TheBasP allows interpretation as a channel-coding problem, and it guaranteeserror-free reconstruction with a properly chosen measurement matrix andsufficiently sparse error vectors. In this manuscript, we examine how the BasPperforms on a given measurement matrix and develop an algorithm to discover thesparsest vectors for which the BasP fails. The resulting algorithm is ageneralization of our previous results on finding the most probableerror-patterns degrading performance of a finite size Low-Density Parity-Check(LDPC) code in the error-floor regime. The BasP fails when its output isdifferent from the actual error-pattern. We design a CS-Instanton SearchAlgorithm (ISA) generating a sparse vector, called a CS-instanton, such thatthe BasP fails on the CS-instanton, while the BasP recovery is successful forany modification of the CS-instanton replacing a nonzero element by zero. Wealso prove that, given a sufficiently dense random input for the error-vector,the CS-ISA converges to an instanton in a small finite number of steps. Theperformance of the CS-ISA is illustrated on a randomly generated $120\times512$ matrix. For this example, the CS-ISA outputs the shortest instanton (errorvector) pattern of length 11.
展开▼
